package org.example.dp.split;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/13 18:21
 */
public class Solution279 {

    public static void main(String[] args) {
        Solution279 solution279 = new Solution279();
        System.out.println(solution279.numSquares(12));
    }

    public int numSquares(int n) {

        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int i=1;i<=n;i++){
            dp[i] = Integer.MAX_VALUE;
            for(int j=1;j*j<=i;j++){
                dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
            }
        }

        return dp[n];
    }
}
